package LimitedTimeGame.Day_0206;

/**
 * @author zxc
 * @date 2023/02/06 09:54
 **/

/**
 * 题目 ：计算布尔二叉树的值
 * 题目详述 ：
 * 给你一棵 完整二叉树的根，这棵树有以下特征：
 * 叶子节点要么值为0要么值为1，其中0 表示False，1 表示True。
 * 非叶子节点 要么值为 2要么值为 3，其中2表示逻辑或OR ，3表示逻辑与AND。
 * 计算一个节点的值方式如下：
 * 如果节点是个叶子节点，那么节点的 值为它本身，即True或者False。
 * 否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行 运算。
 * 返回根节点root的布尔运算值。
 * 完整二叉树是每个节点有 0个或者 2个孩子的二叉树。
 * 叶子节点是没有孩子的节点。
 *
 * 提示：
 * 树中节点数目在[1, 1000]之间。
 * 0 <= Node.val <= 3
 * 每个节点的孩子数为0 或2。
 * 叶子节点的值为0或1。
 * 非叶子节点的值为2或3
 *
 */
public class EvaluateTree {
    public static void main(String[] args) {
    }
    /**
     * 思路：
     * 递归获取二叉树每一个节点的值
     * ===》
     * 步骤 ：
     * （1）递归结束条件，即 node == null，代表了当前遍历的二叉树节点为空;
     * （2）左右子节点，逐步进行遍历，直至叶子节点;
     * （3）同时，将非叶子节点的值，根据叶子节点来进行求解出来;
     * ===》 特殊情况
     * （4）若是当前节点为叶子节点的话，即直接返回当前叶子节点所代表的值即可;
     *
     * @param root
     * @return
     */
    public boolean evaluateTree(TreeNode root) {
        return recursion(root);
    }

    private Boolean recursion(TreeNode node) {
        if(node == null){
            return null;
        }
        if(node.val == 2 || node.val == 3){
            // 即，通过left && right变量，来记录当前遍历的节点,左右子节点的值;
            Boolean left = recursion(node.left);
            Boolean right = recursion(node.right);
            System.out.println("left : " + left + ", right : " + right + ", node.val : " + node.val);
            if(node.val == 2){
                return (left == null ? false : left) || (right == null ? false : right);
            }
            else{
                return (left == null ? true : left) && (right == null ? true : right);
            }
        }
        else {
            return node.val == 1;
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
        }
    }
}
